package search;

import java.util.ArrayList;
import java.util.Arrays;

public class FibonacciSearch implements MySearch {
    private static final int SIZE=20;
    private int searchCount=0;

    @Override
    public int getSearchCount() {
        return searchCount;
    }

    public static void main(String[] args) {
        //int[] a = {16,52,61,61,88,124,159,561,1024,10001,200000};
        int[] a = {16,22,35,46,52,61,71,88,124,159,201,301};
        //int[] a={88,88,88,88,88,88,88,88,88,88,88,88,88};
        FibonacciSearch search = new FibonacciSearch();
        int result = search.search(a,88);
        System.out.println(result);
        System.out.println("查找次数："+search.getSearchCount());
        //System.out.println("查找结果:"+result);
        //int[] result = ((FibonacciSearch)search).createFibonacciArray(20);
        //System.out.println(Arrays.toString(result));
    }

    @Override
    public int search(int[] array, int value) {
        int[] fa = createFibonacciArray(array.length);
        int k = fa.length-1;
        int[] temp = array;
        if(array.length<fa[k]){
            temp = Arrays.copyOf(array,fa[k]);
            for(int i=array.length;i<temp.length-1;i++){
                temp[i] = array[array.length-1];
            }
        }
        int left=0;
        int right=temp.length-1;
        while(left<=right){
            int mid = left+fa[k-1];
            if(value<temp[mid]){
                right=mid-1;
                k--;
            }else if(value>temp[mid]){
                left=mid+1;
                k-=2;
            }else {
                return mid;
            }
            searchCount++;
        }
        return -1;
    }
    public int[] createFibonacciArray(int range){
        int maxVal=0;
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(0);
        arrayList.add(1);
        for(int i=2;i<SIZE;i++){
            maxVal=arrayList.get(i-1)+arrayList.get(i-2);
            arrayList.add(maxVal);
            if(maxVal>=range){
                break;
            }
        }
        return arrayList.stream().mapToInt(Integer::valueOf).toArray();
    }
    @Override
    public int[] searchs(int[] array, int value) {
        return new int[0];
    }
}
